In general, a reasoning function is an essential function of lots of semantic web tools. A rule-based reasoning method has become one of most widely used reasoning schemes since a Rete algorithm was developed in 1979. The Rete algorithm was originally developed for the efficiency of a generation rule system and is an algorithm also suitable for rule-based ontology reasoning. Here, the rule refers to an ‘if-then’ rule, which consists of the left side LHS and the right side RHS. The LHS consists of one or more conditions, and the RHS is executed when the conditions are met.
In ontology, one fact consists of the subject, a predicate, and an object, and each condition is commonly represented by a triple pattern.
Here, the triple pattern means that one or more of the subject, a predicate, and an object of the triple may be variables. The RHS is a conclusion and is also composed of one or more triple patterns. All variables of the RHS must appear in the LHS once or more. If the LHS are matched with the facts of ontology and variables thereof are assigned specific values, the RHS generates a new fact by applying the same variable-value allocation.
In rule-based ontology reasoning, the Rete algorithm is widely used owing to the efficiency of pattern matching. The efficiency lies in that the repetitive matching between patterns shared by several rules can be avoided. The algorithm may also be used in rule-based ontology reasoning by modifying a Task Memory Element (WME) so that it can handle a triple.
Ontology is chiefly written in RDF, RDF/S, and OWL languages. The languages consist of several defined vocabularies. Several entailment rules may be derived from the meanings of the vocabularies. The vocabularies are defined to describe ontology itself. The entailment rules are comprehensive and always valid for specific ontology, and thus commonly having a wild pattern.
An entailment rule having a wild pattern, that is, a wild pattern rule may further deteriorate inefficiency in case of reasoning on large-sale ontology. The large-scale ontology systems are utilized as depositories based on database engines, such as an MS SQL server, ORACLE, and MySQL. Here, triples are chiefly stored according to classes and properties for efficiency. The Rete algorithm may be used for reasoning, but it may be impossible to maintain alpha memory and beta memory of Rete in main memory. One solution is to make alpha memory and beta memory refer to relevant tables through a database view scheme. In this case, alpha memory corresponding to a specific triple pattern must refer to all triple tables, which may cause inefficiency that an unnecessary table is accessed when join is performed at a linked join node.